package kyssion.leetcode.num1_50;

public class code50_pow_x_y_实现powxy函数 {
    public static void main(String[] args) {
        System.out.println(new code50_pow_x_y_实现powxy函数().myPow2(2, 5000));
    }

    /**
     * 这种for循环会超时
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        double item = 1;
        if (n > 0) {
            for (int a = 0; a < n; a++) {
                item = item * x;
                if (item > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                } else if (item < Integer.MIN_VALUE) {
                    return Integer.MIN_VALUE;
                }
            }
        } else if (n < 0) {
            n = -n;

            for (int a = 0; a < n; a++) {
                item = item * x;
                if (item > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                } else if (item < Integer.MIN_VALUE) {
                    return Integer.MIN_VALUE;
                }
            }
            item = 1 / item;
        }
        return item;
    }

    /**
     * 使用二分 降低成logn的复杂度
     * 其实这个是快速幂
     * 这个算法的灵感我觉得是来自于二进制的快速手算转化方法
     * 比如 10
     * 使用二进制的时候将会生成一个计算队列
     *   0 | 10
     *   - 1 | 5
     *   - - 0 | 2
     *   - - - 1 | 1
     *   其实得到10的方法就是 计算过程中的每一个1都记录求和就行了
     *   转化成乘法就是 快速幂
     * @param x
     * @param n
     * @return
     */
    public double myPow2(double x, int n) {
        double res = 0;
        x = 1;
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 != 0) {
                res += x;//补正
            }
            x += x;
        }
        return n < 0 ? 1 / res : res;
    }
}
